class Solution
{
public:
    int maxTotalReward(vector<int> &rewardValues)
    {
        sort(rewardValues.begin(), rewardValues.end());
        vector<int> cache(rewardValues.back() * 2, -1);
        cache[0] = 1;

        function<bool(int)> canConstruct = [&](int target)
        {
            if (cache[target] != -1)
            {
                return cache[target];
            }
            auto it = lower_bound(rewardValues.begin(), rewardValues.end(), target);
            if (it != rewardValues.end() && *it == target)
            {
                return cache[target] = true;
            }
            while (it != rewardValues.begin())
            {
                --it;
                if (*it <= target / 2)
                {
                    break;
                }
                if (canConstruct(target - *it))
                {
                    return cache[target] = true;
                }
            }
            return cache[target] = false;
        };
        for (int t = 2 * rewardValues.back() - 1; t >= 1; --t)
        {
            if (canConstruct(t))
            {
                return t;
            }
        }
        return 0;
    }
};